/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr || list2 == nullptr) {
            if (list1 == nullptr)return list2;
            if (list2 == nullptr)return list1;
        }
        ListNode* newhead = new ListNode;
        ListNode* cur1 = list1;
        ListNode* cur2 = list2;
        ListNode* tail = newhead;
        while (cur1 && cur2) {
            if (cur1->val < cur2->val) {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail = tail->next;
        }
        if (cur1)tail->next = cur1;
        if (cur2)tail->next = cur2;
        return newhead->next;
    }

};